#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
const int k = 1e6, K = k + 5;
const LL inf = 1e18;

int n, a[N]; LL s[N], f[K];

LL t[K << 2], tag[K << 2];
void Pushup(int u) { t[u] = max(t[u << 1], t[u << 1 | 1]); }
void Maketag(int u, LL x) { t[u] += x, tag[u] += x; }
void Pushdown(int u) {
  if (tag[u])
    Maketag(u << 1, tag[u]),
    Maketag(u << 1 | 1, tag[u]),
    tag[u] = 0;
}
void Update(int ql, int qr, LL x, int l, int r, int u) {
  if (ql > qr) return ;
  if (ql <= l && r <= qr) return Maketag(u, x);
  Pushdown(u); int mid = l + r >> 1;
  if (ql <= mid) Update(ql, qr, x, l, mid, u << 1);
  if (qr > mid) Update(ql, qr, x, mid + 1, r, u << 1 | 1);
  Pushup(u);
}
void Modify(int x, LL y, int l, int r, int u) {
  if (l == r) return t[u] = max(t[u], y), void();
  Pushdown(u); int mid = l + r >> 1;
  if (x <= mid) Modify(x, y, l, mid, u << 1);
  else Modify(x, y, mid + 1, r, u << 1 | 1);
  Pushup(u);
}
LL Query(int ql, int qr, int l, int r, int u) {
  if (ql > qr) return -inf;
  if (ql <= l && r <= qr) return t[u];
  Pushdown(u); int mid = l + r >> 1; LL res = -inf;
  if (ql <= mid) res = max(res, Query(ql, qr, l, mid, u << 1));
  if (qr > mid) res = max(res, Query(ql, qr, mid + 1, r, u << 1 | 1));
  return res;
}

void mian() {
  cin >> n;
  F(i, 1, n) cin >> a[i];
  F(i, 1, n) s[i] = s[i - 1] + (a[i] == a[i - 1] ? a[i] : 0);
  s[n + 1] = s[n], a[n + 1] = 0;
  LL ans = s[n], tmp = f[0] = 0; F(i, 1, k) f[i] = -inf;
  F(i, 1, k + 1 << 2) t[i] = -inf, tag[i] = 0;
  F(i, 1, n) {
    LL cal = max(Query(a[i], a[i], 0, k, 1) + a[i], t[1]) - s[i];
    if (a[i] == a[i - 1]) Update(0, k, a[i], 0, k, 1);
    Modify(a[i - 1], max(f[a[i]] + a[i], tmp) + s[i - 1], 0, k, 1);
    f[a[i - 1]] = max(f[a[i - 1]], cal), tmp = max(tmp, cal);
    ans = max(ans, t[1] + s[n] - s[i + 1]);
    ans = max(ans, Query(a[i + 1], a[i + 1], 0, k, 1) + a[i + 1] + s[n] - s[i + 1]);
  }
  cout << ans << "\n";
}

int main() {
  freopen("color.in", "r", stdin);
  freopen("color.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _; cin >> _; while (_--) mian();
  return 0;
}